package advanced.class01;

//左神进阶班第一课，最大的搜索二叉树的拓扑结构（没讲）
public class Question07_MaxSearchTreeTuo {

    // 定义Node节点
    public static class Node{
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value=data;
        }
    }

    //***************************************解法一********************************************************
    // 定义主函数入口
    public static int getMaxSize(Node root) {
        // 如果当前的root为null，直接返回0
        if(root == null) return 0;
        // 计算以当前root为根节点的最大拓扑二叉搜索树的大小
        int max = maxTuoSize(root,root);
        // 递归进入计算左子树的过程，与原始的max进行比较
        max = Math.max(max,getMaxSize(root.left));
        // 递归进入计算右子树的过程，与更新的max进行比较
        max = Math.max(max,getMaxSize(root.right));
        // 返回结果
        return max;
    }

    // 获取以root为根节点的最大拓扑结构（该拓扑树一定包含root节点）
    private static int maxTuoSize(Node root, Node cur) {
        // 如果当前的cur在以root为根节点的搜索二叉树中
        if(cur != null && isBSTNode(root,cur)) {
            // 左边的结果加中间的结果再加1
            return maxTuoSize(root,cur.left) + maxTuoSize(root,cur.right) + 1;
        }
        return 0;
    }

    // 检查cur节点是否存在于以root为根节点的搜索二叉树中
    private static boolean isBSTNode(Node root, Node cur) {
        if(root == null) {
            return false;
        }
        if(cur == root) {
            return true;
        }
        return isBSTNode(root.value > cur.value ? root.left : root.right, cur);
    }


    //***************************************解法二********************************************************
    //主函数入口
    public static int getMaxSize2(Node root) {
        if(root == null) return 0;
        return getMaxRes(root)[1];
    }

    // 获取以当前root为根节点，我们想要的信息
    // int[0]表示以当前root节点为根节点的二叉搜索树的大小记位n1
    // int[1]表示以当前root节点 为根节点的树中最大拓扑二叉树结构的大小
    private static int[] getMaxRes(Node root) {
        if(root == null) return new int[]{0,0};
        if(root.left == null && root.right == null) return new int[]{1,1};
        int[] left = getMaxRes(root.left);
        int[] right = getMaxRes(root.right);
        // 1. 如果root.left == null
        if(root.left == null) {
            if(root.value < root.right.value){
                return new int[]{right[0] + 1, Math.max(right[0] + 1,right[1])};
            }else{
                return new int[]{1,right[1]};
            }
        }
        //2. 如果root.right == null
        if(root.right == null) {
            if(root.value > root.left.value){
                return new int[]{left[0] + 1, Math.max(left[0] + 1,left[1])};
            }else{
                return new int[]{1,left[1]};
            }
        }
        //3. 如果当前的root和其左右字节点可以组成二叉树
        if(root.value > root.left.value && root.value < root.right.value){
            return new int[]{left[0] + right[0] + 1,Math.max(left[0] + right[0] + 1, Math.max(left[1],right[1]))};
        }
        if(root.value > root.left.value){
            return new int[]{left[0] + 1,Math.max(left[0] + 1, right[1])};
        }
        if(root.value < root.right.value){
            return new int[]{right[0] + 1,Math.max(right[0] + 1,left[1])};
        }
        return new int[]{1,Math.max(left[1],right[1])};
    }


    // for test -- print tree
    public static void printTree(Node head) {
        System.out.println("Binary Tree:");
        printInOrder(head, 0, "H", 17);
        System.out.println();
    }

    public static void printInOrder(Node head, int height, String to, int len) {
        if (head == null) {
            return;
        }
        printInOrder(head.right, height + 1, "v", len);
        String val = to + head.value + to;
        int lenM = val.length();
        int lenL = (len - lenM) / 2;
        int lenR = len - lenM - lenL;
        val = getSpace(lenL) + val + getSpace(lenR);
        System.out.println(getSpace(height * len) + val);
        printInOrder(head.left, height + 1, "^", len);
    }

    public static String getSpace(int num) {
        String space = " ";
        StringBuffer buf = new StringBuffer("");
        for (int i = 0; i < num; i++) {
            buf.append(space);
        }
        return buf.toString();
    }

    public static void main(String []args) {
        //System.out.println("Hello");
        Node node=new Node(12);
        node.left=new Node(10);
        node.right=new Node(13);
        node.left.left=new Node(4);
        node.left.right=new Node(14);
        node.right.left=new Node(20);
        node.right.right=new Node(16);
        node.left.left.left=new Node(2);
        node.left.left.right=new Node(5);
        node.left.right.left=new Node(11);
        node.left.right.right=new Node(15);
        printTree(node);

        System.out.println(getMaxSize(node));
        //System.out.println(getMaxSize2(node));
    }
}
